/*
 * @lc app=leetcode.cn id=807 lang=cpp
 *
 * [807] 保持城市天际线
 */

// @lc code=start
class Solution
{
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>> &grid)
    {
        //城市天际线 四周看过来也就是确定各个方向看过来的最高点
        //只需要看左和上
        vector<int> left; //从左边看到的天际线 最大值
        for (int i = 0; i < grid.size(); i++)
        {
            int tmp = 0;
            for (int j = 0; j < grid[0].size(); j++)
            {
                tmp = max(tmp, grid[i][j]); //寻找一行中的最大值
            }
            left.push_back(tmp);
        }
        vector<int> on1; //从上边看到的天际线 最大值
        for (int i = 0; i < grid[0].size(); i++)
        {
            int tmp = 0;
            for (int j = 0; j < grid.size(); j++)
            {
                tmp = max(tmp, grid[j][i]); //寻找一列中的最大值
            }
            on1.push_back(tmp);
        }
        //这里left相当于行 on1代表列
        int res = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                int tmp = 0;
                tmp = min(left[i], on1[j]); //取较小值
                res += (tmp - grid[i][j]);
            }
        }
        return res;
    }
};
// @lc code=end
